home *** CD-ROM | disk | FTP | other *** search
/ Aminet 12 / Aminet 12 (1996)(GTI - Schatztruhe)[!][Jun 1996].iso / Aminet / dev / e / framework.lha / fw / dictionary.e < prev    next >
Encoding:
Text File  |  1996-01-28  |  2.0 KB  |  80 lines
  1.  
  2. -> dictionary is an efficient data structure for named objects.
  3. -> Time complexity for data adding is O(log n).
  4. -> Time complexity for data searching is also O(log n).
  5. -> Space complexity is O(n).
  6.  
  7. -> Copyright © Guichard Damien 01/04/1996
  8.  
  9. OPT MODULE
  10. OPT EXPORT
  11.  
  12. MODULE 'fw/sortedTree'
  13.  
  14. OBJECT dictionary OF sortedTree
  15.   name:PTR TO CHAR
  16. ENDOBJECT
  17.  
  18. -> Creation method.
  19. -> MUST precede any call to a method, str MUST be non NULL.
  20. PROC create(str) OF dictionary
  21.   self.name:=str
  22. ENDPROC
  23.  
  24. -> Is object less than other.
  25. PROC isLessThan(other:PTR TO dictionary) OF dictionary
  26. ENDPROC OstrCmp(other.name,self.name,ALL)=-1
  27.  
  28. -> Is object egal to other.
  29. PROC isEqualTo(other:PTR TO dictionary) OF dictionary
  30. ENDPROC StrCmp(other.name,self.name,ALL)
  31.  
  32. -> Is object greater than other.
  33. PROC isGreaterThan(other:PTR TO dictionary) OF dictionary
  34. ENDPROC OstrCmp(other.name,self.name,ALL)=1
  35.  
  36. -> Find an element in the tree.
  37. -> The first matching element is returned.
  38. -> Use continu() to find next occurrences.
  39. PROC find(key:PTR TO CHAR) OF dictionary
  40.   DEF c
  41.   LOOP
  42.     IF self=NIL THEN RETURN NIL
  43.     c:=OstrCmp(self.name,key,ALL)
  44.     IF c=-1
  45.       self:=self.left
  46.     ELSEIF c=1
  47.       self:=self.right
  48.     ELSE
  49.       RETURN self
  50.     ENDIF
  51.   ENDLOOP
  52. ENDPROC
  53.  
  54. -> Find next element in the tree that has same name.
  55. -> Usually this is used on element returned by find.
  56. PROC continu() OF dictionary
  57.   DEF more:PTR TO dictionary
  58.   IF (more:=self.right)=NIL THEN RETURN NIL
  59. ENDPROC more.find(self.name)
  60.  
  61. -> Print a readeable form of the object to standard output.
  62. PROC out() OF dictionary
  63.   VfPrintf(stdout,'\s ',[self.name])
  64. ENDPROC
  65.  
  66. -> NEVER call this method. Use loadObject() instead.
  67. PROC load() OF dictionary
  68.   IF self.name  THEN self.name :=self.loadString()
  69.   IF self.left  THEN self.left :=self.loadObject()
  70.   IF self.right THEN self.right:=self.loadObject()
  71. ENDPROC
  72.  
  73. -> NEVER call this method. Use storeObject() instead.
  74. PROC store() OF dictionary
  75.   IF self.name  THEN self.storeString(self.name)
  76.   IF self.left  THEN self.left.storeObject()
  77.   IF self.right THEN self.right.storeObject()
  78. ENDPROC
  79.  
  80.